<?xml version="1.0" encoding="UTF-8"?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.1//EN"
       "http://www.w3.org/TR/xhtml11/DTD/xhtml11-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
	<title>
		点选算法
	</title>
	<style type="text/css">
		@import url("../css/function.css");
	</style>
</head>
<body>
	<h1 id='htitle'>
		点选算法
	</h1>
<a href="../index.html">返回主索引</a>
<hr /><!--"----------------------------------------"-->
<p>其实点选算法已经有很多的涉及。GEOS库中也有相应的函数可调。但是我为什么要单独设计这个算法呢？因为GEOS中的算法很慢，特别是多边形非常复杂的时候。开始以为是Python效率问题，后面才发现在C++中也是一样的慢(QGIS的多边形点选也是同样的速度，这大概是GEOS自己的问题)。有的时候慢到一种让人无法忍受的地步，大概纯粹的数学算法的速度就是这个样子吧。所以不得不采用另一种方案来处理多边形的点选问题。我看ArcView3.2，可以做到点了马上就能判断点是否在多边形内的效果。所以我觉得如果不是GEOS的纯数学算法有问题，就是ArcView采用了其他算法。
</p>
<p>我采用的方法是栅格法来处理矢量点选问题。因为我发现，在绘制同一个多边形的时候的速度远比点选判断的速度要快得多。既然绘制更快，我们就可以通过在内存中绘制多边形后点所在位置的图像象元值来判断点是否在多边形内部，也就是通过绘制来判断拓扑关系。呵呵，我第一次想到的时候觉得很玄妙。居然可以用栅格来进行矢量的拓扑计算，这也可以算栅格和矢量结合的一个例子吧。
</p>
<p>方法很简单，具体的说，就是把要判断是否包含点的多边形画到一个内存区域中－－这个过程可以由很多方法实现，比如用PIL直接对内存进行绘制（这个过程会有问题，等下会涉及到）或者用wx的MemoryDC来进行内存中绘制，这个过程无所谓用何种方法－－然后把所要判断的点定位到内存区域的某个位置。察看这个位置的像素值就可以判断该点是否在多边形区域内。至于像素值的判断就要看绘制方法了。比如画笔的选定，等等。
</p>
<p>举个例子，我们要判断点P是否在多边形A内，我们就先开辟一个显示大小的内存DC，设置底色为白，然后用黑笔在多边形在DC中所处位置进行绘制和填充多边形。然后把点P的位置换算到DC中，察看点P所在位置的象元颜色，如果为白，则不在多边形内，如果为黑，则在多边形内（或在外边界上）。
</p>
<p>当然，多边形有可能很大，有可能超出屏幕范围非常多。是否内存区域也需要那么大呢？当然不需要，我们最多需要屏幕大小的区域就足够了。超出屏幕区域的范围，就让画笔自己去判断吧（感觉这个过程在很多绘制API中应该都有加速）。而对于点选在边缘是否准确，这个可以不用担心。因为我们的点选也就是在屏幕上点，至于一个像素中包含了成百上千的多边形点我们也不需要管那么多。只要我们点选的点在屏幕上，就不用考虑这么多。因为这都是在估算的层面上进行的。如果需要在理论上进行非常精确的点选运算，建议用GEOS这样的纯数学判断方法。
</p>
<p>当然，这样的算法有问题。多边形包括洞和岛，岛倒是没什么，因为虽然分离当在DC中画出来还是黑乎乎的一片。洞的问题就比较大。要看选择什么样的绘图API和笔。如果画过一遍后，值还是原来的颜色，就没法判断是否是在多边形内部了，因为洞需要挖空，而绘图笔是重新上色。这就需要特殊笔来处理。现在有两种方法来解决，一种是用透明色，A值采用小于255的颜色，绘制后通过A值是否为一次绘制值来判断（如果反复涂抹同一区域，A值会叠加，不过这样大概影响绘制效率），另外可以用XOR笔来进行绘制，涂抹一次黑色，再涂抹第二次时，XOR在计算黑色加黑色时就恢复了原来的底色。
</p>
<p>九形通过这种方法，差不多做到了ArcView的点了就能选出的效果。比纯粹用GEOS的快了很多。我的实现请参看九形的源代码geosings.core.Layer.VectorLayer.SelectFeaturesByPoint函数。（不过有一点，我现在的实现还是在PIL的绘制API下进行的，PIL的API仿佛不支持XOR画笔，所以洞还是有问题的）
</p>
<p>
</p>
<hr /><!--"----------------------------------------"-->
<br />

<table id='etab'>
	<td id='etit'>geosings, 点选算法</td>
	<td id='ereta'><a href='../index.html'>返回主目录</a></td>
</table>

</body>
</html>

